package DP.子序列;

import org.junit.Test;

import static MyUtils.MHUtils.*;
import static MyUtils.MHMoban.*;

/*
     dp[i][j]：前(i,j)中的最大公共序长度

     初始化0j时,'前': 虽要记忆，但不是累和
      [因为(a aaaa) 应该是 1111 最长就1个公共

     相同时同时-1,为什么不考虑(i-1,j)?
      因为我就拿个数而已,又不牵扯改动(i-1,j)
 */
public class 最长公共子序列1143 {
    @Test
    public void test() {
        //System.out.println(longestCommonSubsequence("abcde","ace"));
        System.out.println(longestCommonSubsequence("aaa","aaaaa"));
    }

    public int longestCommonSubsequence(String t1, String t2) {
        char[] s1 = t1.toCharArray(), s2 = t2.toCharArray();
        int n1 = s1.length, n2 = s2.length;
        int[][] dp = new int[n1][n2];
        //由下方初始化j-1,致这里要单独先初始化
        dp[0][0] = s1[0]==s2[0]?1:0;
        for (int j = 1; j < dp[0].length; j++) {
            dp[0][j] = s1[0]==s2[j]?
                            //dp[0][j-1]+1:
                            1:
                            dp[0][j-1];
        }
        for (int i = 1; i < dp.length; i++) {
            dp[i][0] = s1[i]==s2[0]?
                        1:
                        dp[i-1][0];
        }
        //从1走
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length ; j++) {
                //相同:res长度+1 (因为是子序直接无限加,不用像串要考虑可能扔掉前面
                if(s1[i]==s2[j]){
                    //为什么不考虑(i-1,j)? 因为我就拿个数而已,又不牵扯改动(i-1,j)
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                //不同：取1次大的吧（注意我只要最终[n][m]所以这个max只取1次
                else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        //因为是”前“,可以用mn
        return dp[n1-1][n2-1];
    }
}
